<!doctype html>

<html>
<head>
  <link rel="shortcut icon" href="static/images/favicon.ico" type="image/x-icon">
  <title>array.js (Closure Library API Documentation - JavaScript)</title>
  <link rel="stylesheet" href="static/css/base.css">
  <link rel="stylesheet" href="static/css/doc.css">
  <link rel="stylesheet" href="static/css/sidetree.css">
  <link rel="stylesheet" href="static/css/prettify.css">

  <script>
     var _staticFilePath = "static/";
     var _typeTreeName = "goog";
     var _fileTreeName = "Source";
  </script>

  <script src="static/js/doc.js">
  </script>


  <meta charset="utf8">
</head>

<body onload="grokdoc.onLoad();">

<div id="header">
  <div class="g-section g-tpl-50-50 g-split">
    <div class="g-unit g-first">
      <a id="logo" href="index.html">Closure Library API Documentation</a>
    </div>

    <div class="g-unit">
      <div class="g-c">
        <strong>Go to class or file:</strong>
        <input type="text" id="ac">
      </div>
    </div>
  </div>
</div>

<div class="clear"></div>

<h2><a href="closure_goog_array_array.js.html">array.js</a></h2>

<pre class="prettyprint lang-js">
<a name="line1"></a>// Copyright 2006 The Closure Library Authors. All Rights Reserved.
<a name="line2"></a>//
<a name="line3"></a>// Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);
<a name="line4"></a>// you may not use this file except in compliance with the License.
<a name="line5"></a>// You may obtain a copy of the License at
<a name="line6"></a>//
<a name="line7"></a>//      http://www.apache.org/licenses/LICENSE-2.0
<a name="line8"></a>//
<a name="line9"></a>// Unless required by applicable law or agreed to in writing, software
<a name="line10"></a>// distributed under the License is distributed on an &quot;AS-IS&quot; BASIS,
<a name="line11"></a>// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
<a name="line12"></a>// See the License for the specific language governing permissions and
<a name="line13"></a>// limitations under the License.
<a name="line14"></a>
<a name="line15"></a>/**
<a name="line16"></a> * @fileoverview Utilities for manipulating arrays.
<a name="line17"></a> *
<a name="line18"></a> */
<a name="line19"></a>
<a name="line20"></a>
<a name="line21"></a>goog.provide(&#39;goog.array&#39;);
<a name="line22"></a>goog.provide(&#39;goog.array.ArrayLike&#39;);
<a name="line23"></a>
<a name="line24"></a>goog.require(&#39;goog.asserts&#39;);
<a name="line25"></a>
<a name="line26"></a>
<a name="line27"></a>/**
<a name="line28"></a> * @define {boolean} NATIVE_ARRAY_PROTOTYPES indicates whether the code should
<a name="line29"></a> * rely on Array.prototype functions, if available.
<a name="line30"></a> *
<a name="line31"></a> * The Array.prototype functions can be defined by external libraries like
<a name="line32"></a> * Prototype and setting this flag to false forces closure to use its own
<a name="line33"></a> * goog.array implementation.
<a name="line34"></a> *
<a name="line35"></a> * If your javascript can be loaded by a third party site and you are wary about
<a name="line36"></a> * relying on the prototype functions, specify
<a name="line37"></a> * &quot;--define goog.NATIVE_ARRAY_PROTOTYPES=false&quot; to the JSCompiler.
<a name="line38"></a> *
<a name="line39"></a> * Setting goog.TRUSTED_SITE to false will automatically set
<a name="line40"></a> * NATIVE_ARRAY_PROTOTYPES to false.
<a name="line41"></a> */
<a name="line42"></a>goog.NATIVE_ARRAY_PROTOTYPES = goog.TRUSTED_SITE;
<a name="line43"></a>
<a name="line44"></a>
<a name="line45"></a>/**
<a name="line46"></a> * @typedef {Array|NodeList|Arguments|{length: number}}
<a name="line47"></a> */
<a name="line48"></a>goog.array.ArrayLike;
<a name="line49"></a>
<a name="line50"></a>
<a name="line51"></a>/**
<a name="line52"></a> * Returns the last element in an array without removing it.
<a name="line53"></a> * @param {goog.array.ArrayLike} array The array.
<a name="line54"></a> * @return {*} Last item in array.
<a name="line55"></a> */
<a name="line56"></a>goog.array.peek = function(array) {
<a name="line57"></a>  return array[array.length - 1];
<a name="line58"></a>};
<a name="line59"></a>
<a name="line60"></a>
<a name="line61"></a>/**
<a name="line62"></a> * Reference to the original {@code Array.prototype}.
<a name="line63"></a> * @private
<a name="line64"></a> */
<a name="line65"></a>goog.array.ARRAY_PROTOTYPE_ = Array.prototype;
<a name="line66"></a>
<a name="line67"></a>
<a name="line68"></a>// NOTE(arv): Since most of the array functions are generic it allows you to
<a name="line69"></a>// pass an array-like object. Strings have a length and are considered array-
<a name="line70"></a>// like. However, the &#39;in&#39; operator does not work on strings so we cannot just
<a name="line71"></a>// use the array path even if the browser supports indexing into strings. We
<a name="line72"></a>// therefore end up splitting the string.
<a name="line73"></a>
<a name="line74"></a>
<a name="line75"></a>/**
<a name="line76"></a> * Returns the index of the first element of an array with a specified
<a name="line77"></a> * value, or -1 if the element is not present in the array.
<a name="line78"></a> *
<a name="line79"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-indexof}
<a name="line80"></a> *
<a name="line81"></a> * @param {goog.array.ArrayLike} arr The array to be searched.
<a name="line82"></a> * @param {*} obj The object for which we are searching.
<a name="line83"></a> * @param {number=} opt_fromIndex The index at which to start the search. If
<a name="line84"></a> *     omitted the search starts at index 0.
<a name="line85"></a> * @return {number} The index of the first matching array element.
<a name="line86"></a> */
<a name="line87"></a>goog.array.indexOf = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line88"></a>                     goog.array.ARRAY_PROTOTYPE_.indexOf ?
<a name="line89"></a>    function(arr, obj, opt_fromIndex) {
<a name="line90"></a>      goog.asserts.assert(arr.length != null);
<a name="line91"></a>
<a name="line92"></a>      return goog.array.ARRAY_PROTOTYPE_.indexOf.call(arr, obj, opt_fromIndex);
<a name="line93"></a>    } :
<a name="line94"></a>    function(arr, obj, opt_fromIndex) {
<a name="line95"></a>      var fromIndex = opt_fromIndex == null ?
<a name="line96"></a>          0 : (opt_fromIndex &lt; 0 ?
<a name="line97"></a>               Math.max(0, arr.length + opt_fromIndex) : opt_fromIndex);
<a name="line98"></a>
<a name="line99"></a>      if (goog.isString(arr)) {
<a name="line100"></a>        // Array.prototype.indexOf uses === so only strings should be found.
<a name="line101"></a>        if (!goog.isString(obj) || obj.length != 1) {
<a name="line102"></a>          return -1;
<a name="line103"></a>        }
<a name="line104"></a>        return arr.indexOf(obj, fromIndex);
<a name="line105"></a>      }
<a name="line106"></a>
<a name="line107"></a>      for (var i = fromIndex; i &lt; arr.length; i++) {
<a name="line108"></a>        if (i in arr &amp;&amp; arr[i] === obj)
<a name="line109"></a>          return i;
<a name="line110"></a>      }
<a name="line111"></a>      return -1;
<a name="line112"></a>    };
<a name="line113"></a>
<a name="line114"></a>
<a name="line115"></a>/**
<a name="line116"></a> * Returns the index of the last element of an array with a specified value, or
<a name="line117"></a> * -1 if the element is not present in the array.
<a name="line118"></a> *
<a name="line119"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-lastindexof}
<a name="line120"></a> *
<a name="line121"></a> * @param {goog.array.ArrayLike} arr The array to be searched.
<a name="line122"></a> * @param {*} obj The object for which we are searching.
<a name="line123"></a> * @param {?number=} opt_fromIndex The index at which to start the search. If
<a name="line124"></a> *     omitted the search starts at the end of the array.
<a name="line125"></a> * @return {number} The index of the last matching array element.
<a name="line126"></a> */
<a name="line127"></a>goog.array.lastIndexOf = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line128"></a>                         goog.array.ARRAY_PROTOTYPE_.lastIndexOf ?
<a name="line129"></a>    function(arr, obj, opt_fromIndex) {
<a name="line130"></a>      goog.asserts.assert(arr.length != null);
<a name="line131"></a>
<a name="line132"></a>      // Firefox treats undefined and null as 0 in the fromIndex argument which
<a name="line133"></a>      // leads it to always return -1
<a name="line134"></a>      var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex;
<a name="line135"></a>      return goog.array.ARRAY_PROTOTYPE_.lastIndexOf.call(arr, obj, fromIndex);
<a name="line136"></a>    } :
<a name="line137"></a>    function(arr, obj, opt_fromIndex) {
<a name="line138"></a>      var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex;
<a name="line139"></a>
<a name="line140"></a>      if (fromIndex &lt; 0) {
<a name="line141"></a>        fromIndex = Math.max(0, arr.length + fromIndex);
<a name="line142"></a>      }
<a name="line143"></a>
<a name="line144"></a>      if (goog.isString(arr)) {
<a name="line145"></a>        // Array.prototype.lastIndexOf uses === so only strings should be found.
<a name="line146"></a>        if (!goog.isString(obj) || obj.length != 1) {
<a name="line147"></a>          return -1;
<a name="line148"></a>        }
<a name="line149"></a>        return arr.lastIndexOf(obj, fromIndex);
<a name="line150"></a>      }
<a name="line151"></a>
<a name="line152"></a>      for (var i = fromIndex; i &gt;= 0; i--) {
<a name="line153"></a>        if (i in arr &amp;&amp; arr[i] === obj)
<a name="line154"></a>          return i;
<a name="line155"></a>      }
<a name="line156"></a>      return -1;
<a name="line157"></a>    };
<a name="line158"></a>
<a name="line159"></a>
<a name="line160"></a>/**
<a name="line161"></a> * Calls a function for each element in an array. Skips holes in the array.
<a name="line162"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-foreach}
<a name="line163"></a> *
<a name="line164"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array like object over
<a name="line165"></a> *     which to iterate.
<a name="line166"></a> * @param {?function(this: S, T, number, ?): ?} f The function to call for every
<a name="line167"></a> *     element. This function takes 3 arguments (the element, the index and the
<a name="line168"></a> *     array). The return value is ignored.
<a name="line169"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39; within f.
<a name="line170"></a> * @template T,S
<a name="line171"></a> */
<a name="line172"></a>goog.array.forEach = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line173"></a>                     goog.array.ARRAY_PROTOTYPE_.forEach ?
<a name="line174"></a>    function(arr, f, opt_obj) {
<a name="line175"></a>      goog.asserts.assert(arr.length != null);
<a name="line176"></a>
<a name="line177"></a>      goog.array.ARRAY_PROTOTYPE_.forEach.call(arr, f, opt_obj);
<a name="line178"></a>    } :
<a name="line179"></a>    function(arr, f, opt_obj) {
<a name="line180"></a>      var l = arr.length;  // must be fixed during loop... see docs
<a name="line181"></a>      var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line182"></a>      for (var i = 0; i &lt; l; i++) {
<a name="line183"></a>        if (i in arr2) {
<a name="line184"></a>          f.call(opt_obj, arr2[i], i, arr);
<a name="line185"></a>        }
<a name="line186"></a>      }
<a name="line187"></a>    };
<a name="line188"></a>
<a name="line189"></a>
<a name="line190"></a>/**
<a name="line191"></a> * Calls a function for each element in an array, starting from the last
<a name="line192"></a> * element rather than the first.
<a name="line193"></a> *
<a name="line194"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line195"></a> *     like object over which to iterate.
<a name="line196"></a> * @param {?function(this: S, T, number, ?): ?} f The function to call for every
<a name="line197"></a> *     element. This function
<a name="line198"></a> *     takes 3 arguments (the element, the index and the array). The return
<a name="line199"></a> *     value is ignored.
<a name="line200"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39;
<a name="line201"></a> *     within f.
<a name="line202"></a> * @template T,S
<a name="line203"></a> */
<a name="line204"></a>goog.array.forEachRight = function(arr, f, opt_obj) {
<a name="line205"></a>  var l = arr.length;  // must be fixed during loop... see docs
<a name="line206"></a>  var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line207"></a>  for (var i = l - 1; i &gt;= 0; --i) {
<a name="line208"></a>    if (i in arr2) {
<a name="line209"></a>      f.call(opt_obj, arr2[i], i, arr);
<a name="line210"></a>    }
<a name="line211"></a>  }
<a name="line212"></a>};
<a name="line213"></a>
<a name="line214"></a>
<a name="line215"></a>/**
<a name="line216"></a> * Calls a function for each element in an array, and if the function returns
<a name="line217"></a> * true adds the element to a new array.
<a name="line218"></a> *
<a name="line219"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-filter}
<a name="line220"></a> *
<a name="line221"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line222"></a> *     like object over which to iterate.
<a name="line223"></a> * @param {?function(this:S, T, number, ?):boolean} f The function to call for
<a name="line224"></a> *     every element. This function
<a name="line225"></a> *     takes 3 arguments (the element, the index and the array) and must
<a name="line226"></a> *     return a Boolean. If the return value is true the element is added to the
<a name="line227"></a> *     result array. If it is false the element is not included.
<a name="line228"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39;
<a name="line229"></a> *     within f.
<a name="line230"></a> * @return {!Array} a new array in which only elements that passed the test are
<a name="line231"></a> *     present.
<a name="line232"></a> * @template T,S
<a name="line233"></a> */
<a name="line234"></a>goog.array.filter = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line235"></a>                    goog.array.ARRAY_PROTOTYPE_.filter ?
<a name="line236"></a>    function(arr, f, opt_obj) {
<a name="line237"></a>      goog.asserts.assert(arr.length != null);
<a name="line238"></a>
<a name="line239"></a>      return goog.array.ARRAY_PROTOTYPE_.filter.call(arr, f, opt_obj);
<a name="line240"></a>    } :
<a name="line241"></a>    function(arr, f, opt_obj) {
<a name="line242"></a>      var l = arr.length;  // must be fixed during loop... see docs
<a name="line243"></a>      var res = [];
<a name="line244"></a>      var resLength = 0;
<a name="line245"></a>      var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line246"></a>      for (var i = 0; i &lt; l; i++) {
<a name="line247"></a>        if (i in arr2) {
<a name="line248"></a>          var val = arr2[i];  // in case f mutates arr2
<a name="line249"></a>          if (f.call(opt_obj, val, i, arr)) {
<a name="line250"></a>            res[resLength++] = val;
<a name="line251"></a>          }
<a name="line252"></a>        }
<a name="line253"></a>      }
<a name="line254"></a>      return res;
<a name="line255"></a>    };
<a name="line256"></a>
<a name="line257"></a>
<a name="line258"></a>/**
<a name="line259"></a> * Calls a function for each element in an array and inserts the result into a
<a name="line260"></a> * new array.
<a name="line261"></a> *
<a name="line262"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-map}
<a name="line263"></a> *
<a name="line264"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line265"></a> *     like object over which to iterate.
<a name="line266"></a> * @param {?function(this:S, T, number, ?):?} f The function to call for every
<a name="line267"></a> *     element. This function
<a name="line268"></a> *     takes 3 arguments (the element, the index and the array) and should
<a name="line269"></a> *     return something. The result will be inserted into a new array.
<a name="line270"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39;
<a name="line271"></a> *     within f.
<a name="line272"></a> * @return {!Array} a new array with the results from f.
<a name="line273"></a> * @template T,S
<a name="line274"></a> */
<a name="line275"></a>goog.array.map = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line276"></a>                 goog.array.ARRAY_PROTOTYPE_.map ?
<a name="line277"></a>    function(arr, f, opt_obj) {
<a name="line278"></a>      goog.asserts.assert(arr.length != null);
<a name="line279"></a>
<a name="line280"></a>      return goog.array.ARRAY_PROTOTYPE_.map.call(arr, f, opt_obj);
<a name="line281"></a>    } :
<a name="line282"></a>    function(arr, f, opt_obj) {
<a name="line283"></a>      var l = arr.length;  // must be fixed during loop... see docs
<a name="line284"></a>      var res = new Array(l);
<a name="line285"></a>      var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line286"></a>      for (var i = 0; i &lt; l; i++) {
<a name="line287"></a>        if (i in arr2) {
<a name="line288"></a>          res[i] = f.call(opt_obj, arr2[i], i, arr);
<a name="line289"></a>        }
<a name="line290"></a>      }
<a name="line291"></a>      return res;
<a name="line292"></a>    };
<a name="line293"></a>
<a name="line294"></a>
<a name="line295"></a>/**
<a name="line296"></a> * Passes every element of an array into a function and accumulates the result.
<a name="line297"></a> *
<a name="line298"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-reduce}
<a name="line299"></a> *
<a name="line300"></a> * For example:
<a name="line301"></a> * var a = [1, 2, 3, 4];
<a name="line302"></a> * goog.array.reduce(a, function(r, v, i, arr) {return r + v;}, 0);
<a name="line303"></a> * returns 10
<a name="line304"></a> *
<a name="line305"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line306"></a> *     like object over which to iterate.
<a name="line307"></a> * @param {?function(this:S, R, T, number, ?) : R} f The function to call for
<a name="line308"></a> *     every element. This function
<a name="line309"></a> *     takes 4 arguments (the function&#39;s previous result or the initial value,
<a name="line310"></a> *     the value of the current array element, the current array index, and the
<a name="line311"></a> *     array itself)
<a name="line312"></a> *     function(previousValue, currentValue, index, array).
<a name="line313"></a> * @param {?} val The initial value to pass into the function on the first call.
<a name="line314"></a> * @param {S=} opt_obj  The object to be used as the value of &#39;this&#39;
<a name="line315"></a> *     within f.
<a name="line316"></a> * @return {R} Result of evaluating f repeatedly across the values of the array.
<a name="line317"></a> * @template T,S,R
<a name="line318"></a> */
<a name="line319"></a>goog.array.reduce = function(arr, f, val, opt_obj) {
<a name="line320"></a>  if (arr.reduce) {
<a name="line321"></a>    if (opt_obj) {
<a name="line322"></a>      return arr.reduce(goog.bind(f, opt_obj), val);
<a name="line323"></a>    } else {
<a name="line324"></a>      return arr.reduce(f, val);
<a name="line325"></a>    }
<a name="line326"></a>  }
<a name="line327"></a>  var rval = val;
<a name="line328"></a>  goog.array.forEach(arr, function(val, index) {
<a name="line329"></a>    rval = f.call(opt_obj, rval, val, index, arr);
<a name="line330"></a>  });
<a name="line331"></a>  return rval;
<a name="line332"></a>};
<a name="line333"></a>
<a name="line334"></a>
<a name="line335"></a>/**
<a name="line336"></a> * Passes every element of an array into a function and accumulates the result,
<a name="line337"></a> * starting from the last element and working towards the first.
<a name="line338"></a> *
<a name="line339"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-reduceright}
<a name="line340"></a> *
<a name="line341"></a> * For example:
<a name="line342"></a> * var a = [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;];
<a name="line343"></a> * goog.array.reduceRight(a, function(r, v, i, arr) {return r + v;}, &#39;&#39;);
<a name="line344"></a> * returns &#39;cba&#39;
<a name="line345"></a> *
<a name="line346"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line347"></a> *     like object over which to iterate.
<a name="line348"></a> * @param {?function(this:S, R, T, number, ?) : R} f The function to call for
<a name="line349"></a> *     every element. This function
<a name="line350"></a> *     takes 4 arguments (the function&#39;s previous result or the initial value,
<a name="line351"></a> *     the value of the current array element, the current array index, and the
<a name="line352"></a> *     array itself)
<a name="line353"></a> *     function(previousValue, currentValue, index, array).
<a name="line354"></a> * @param {?} val The initial value to pass into the function on the first call.
<a name="line355"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39;
<a name="line356"></a> *     within f.
<a name="line357"></a> * @return {R} Object returned as a result of evaluating f repeatedly across the
<a name="line358"></a> *     values of the array.
<a name="line359"></a> * @template T,S,R
<a name="line360"></a> */
<a name="line361"></a>goog.array.reduceRight = function(arr, f, val, opt_obj) {
<a name="line362"></a>  if (arr.reduceRight) {
<a name="line363"></a>    if (opt_obj) {
<a name="line364"></a>      return arr.reduceRight(goog.bind(f, opt_obj), val);
<a name="line365"></a>    } else {
<a name="line366"></a>      return arr.reduceRight(f, val);
<a name="line367"></a>    }
<a name="line368"></a>  }
<a name="line369"></a>  var rval = val;
<a name="line370"></a>  goog.array.forEachRight(arr, function(val, index) {
<a name="line371"></a>    rval = f.call(opt_obj, rval, val, index, arr);
<a name="line372"></a>  });
<a name="line373"></a>  return rval;
<a name="line374"></a>};
<a name="line375"></a>
<a name="line376"></a>
<a name="line377"></a>/**
<a name="line378"></a> * Calls f for each element of an array. If any call returns true, some()
<a name="line379"></a> * returns true (without checking the remaining elements). If all calls
<a name="line380"></a> * return false, some() returns false.
<a name="line381"></a> *
<a name="line382"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-some}
<a name="line383"></a> *
<a name="line384"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line385"></a> *     like object over which to iterate.
<a name="line386"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call for
<a name="line387"></a> *     for every element. This function takes 3 arguments (the element, the
<a name="line388"></a> *     index and the array) and should return a boolean.
<a name="line389"></a> * @param {S=} opt_obj  The object to be used as the value of &#39;this&#39;
<a name="line390"></a> *     within f.
<a name="line391"></a> * @return {boolean} true if any element passes the test.
<a name="line392"></a> * @template T,S
<a name="line393"></a> */
<a name="line394"></a>goog.array.some = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line395"></a>                  goog.array.ARRAY_PROTOTYPE_.some ?
<a name="line396"></a>    function(arr, f, opt_obj) {
<a name="line397"></a>      goog.asserts.assert(arr.length != null);
<a name="line398"></a>
<a name="line399"></a>      return goog.array.ARRAY_PROTOTYPE_.some.call(arr, f, opt_obj);
<a name="line400"></a>    } :
<a name="line401"></a>    function(arr, f, opt_obj) {
<a name="line402"></a>      var l = arr.length;  // must be fixed during loop... see docs
<a name="line403"></a>      var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line404"></a>      for (var i = 0; i &lt; l; i++) {
<a name="line405"></a>        if (i in arr2 &amp;&amp; f.call(opt_obj, arr2[i], i, arr)) {
<a name="line406"></a>          return true;
<a name="line407"></a>        }
<a name="line408"></a>      }
<a name="line409"></a>      return false;
<a name="line410"></a>    };
<a name="line411"></a>
<a name="line412"></a>
<a name="line413"></a>/**
<a name="line414"></a> * Call f for each element of an array. If all calls return true, every()
<a name="line415"></a> * returns true. If any call returns false, every() returns false and
<a name="line416"></a> * does not continue to check the remaining elements.
<a name="line417"></a> *
<a name="line418"></a> * See {@link http://tinyurl.com/developer-mozilla-org-array-every}
<a name="line419"></a> *
<a name="line420"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line421"></a> *     like object over which to iterate.
<a name="line422"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call for
<a name="line423"></a> *     for every element. This function takes 3 arguments (the element, the
<a name="line424"></a> *     index and the array) and should return a boolean.
<a name="line425"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39;
<a name="line426"></a> *     within f.
<a name="line427"></a> * @return {boolean} false if any element fails the test.
<a name="line428"></a> * @template T,S
<a name="line429"></a> */
<a name="line430"></a>goog.array.every = goog.NATIVE_ARRAY_PROTOTYPES &amp;&amp;
<a name="line431"></a>                   goog.array.ARRAY_PROTOTYPE_.every ?
<a name="line432"></a>    function(arr, f, opt_obj) {
<a name="line433"></a>      goog.asserts.assert(arr.length != null);
<a name="line434"></a>
<a name="line435"></a>      return goog.array.ARRAY_PROTOTYPE_.every.call(arr, f, opt_obj);
<a name="line436"></a>    } :
<a name="line437"></a>    function(arr, f, opt_obj) {
<a name="line438"></a>      var l = arr.length;  // must be fixed during loop... see docs
<a name="line439"></a>      var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line440"></a>      for (var i = 0; i &lt; l; i++) {
<a name="line441"></a>        if (i in arr2 &amp;&amp; !f.call(opt_obj, arr2[i], i, arr)) {
<a name="line442"></a>          return false;
<a name="line443"></a>        }
<a name="line444"></a>      }
<a name="line445"></a>      return true;
<a name="line446"></a>    };
<a name="line447"></a>
<a name="line448"></a>
<a name="line449"></a>/**
<a name="line450"></a> * Counts the array elements that fulfill the predicate, i.e. for which the
<a name="line451"></a> * callback function returns true. Skips holes in the array.
<a name="line452"></a> *
<a name="line453"></a> * @param {!(Array.&lt;T&gt;|goog.array.ArrayLike)} arr Array or array like object
<a name="line454"></a> *     over which to iterate.
<a name="line455"></a> * @param {function(this: S, T, number, ?): boolean} f The function to call for
<a name="line456"></a> *     every element. Takes 3 arguments (the element, the index and the array).
<a name="line457"></a> * @param {S=} opt_obj The object to be used as the value of &#39;this&#39; within f.
<a name="line458"></a> * @return {number} The number of the matching elements.
<a name="line459"></a> * @template T,S
<a name="line460"></a> */
<a name="line461"></a>goog.array.count = function(arr, f, opt_obj) {
<a name="line462"></a>  var count = 0;
<a name="line463"></a>  goog.array.forEach(arr, function(element, index, arr) {
<a name="line464"></a>    if (f.call(opt_obj, element, index, arr)) {
<a name="line465"></a>      ++count;
<a name="line466"></a>    }
<a name="line467"></a>  }, opt_obj);
<a name="line468"></a>  return count;
<a name="line469"></a>};
<a name="line470"></a>
<a name="line471"></a>
<a name="line472"></a>/**
<a name="line473"></a> * Search an array for the first element that satisfies a given condition and
<a name="line474"></a> * return that element.
<a name="line475"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line476"></a> *     like object over which to iterate.
<a name="line477"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call
<a name="line478"></a> *     for every element. This function takes 3 arguments (the element, the
<a name="line479"></a> *     index and the array) and should return a boolean.
<a name="line480"></a> * @param {S=} opt_obj An optional &quot;this&quot; context for the function.
<a name="line481"></a> * @return {T} The first array element that passes the test, or null if no
<a name="line482"></a> *     element is found.
<a name="line483"></a> * @template T,S
<a name="line484"></a> */
<a name="line485"></a>goog.array.find = function(arr, f, opt_obj) {
<a name="line486"></a>  var i = goog.array.findIndex(arr, f, opt_obj);
<a name="line487"></a>  return i &lt; 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i];
<a name="line488"></a>};
<a name="line489"></a>
<a name="line490"></a>
<a name="line491"></a>/**
<a name="line492"></a> * Search an array for the first element that satisfies a given condition and
<a name="line493"></a> * return its index.
<a name="line494"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line495"></a> *     like object over which to iterate.
<a name="line496"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call for
<a name="line497"></a> *     every element. This function
<a name="line498"></a> *     takes 3 arguments (the element, the index and the array) and should
<a name="line499"></a> *     return a boolean.
<a name="line500"></a> * @param {S=} opt_obj An optional &quot;this&quot; context for the function.
<a name="line501"></a> * @return {number} The index of the first array element that passes the test,
<a name="line502"></a> *     or -1 if no element is found.
<a name="line503"></a> * @template T,S
<a name="line504"></a> */
<a name="line505"></a>goog.array.findIndex = function(arr, f, opt_obj) {
<a name="line506"></a>  var l = arr.length;  // must be fixed during loop... see docs
<a name="line507"></a>  var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line508"></a>  for (var i = 0; i &lt; l; i++) {
<a name="line509"></a>    if (i in arr2 &amp;&amp; f.call(opt_obj, arr2[i], i, arr)) {
<a name="line510"></a>      return i;
<a name="line511"></a>    }
<a name="line512"></a>  }
<a name="line513"></a>  return -1;
<a name="line514"></a>};
<a name="line515"></a>
<a name="line516"></a>
<a name="line517"></a>/**
<a name="line518"></a> * Search an array (in reverse order) for the last element that satisfies a
<a name="line519"></a> * given condition and return that element.
<a name="line520"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line521"></a> *     like object over which to iterate.
<a name="line522"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call
<a name="line523"></a> *     for every element. This function
<a name="line524"></a> *     takes 3 arguments (the element, the index and the array) and should
<a name="line525"></a> *     return a boolean.
<a name="line526"></a> * @param {S=} opt_obj An optional &quot;this&quot; context for the function.
<a name="line527"></a> * @return {T} The last array element that passes the test, or null if no
<a name="line528"></a> *     element is found.
<a name="line529"></a> * @template T,S
<a name="line530"></a> */
<a name="line531"></a>goog.array.findRight = function(arr, f, opt_obj) {
<a name="line532"></a>  var i = goog.array.findIndexRight(arr, f, opt_obj);
<a name="line533"></a>  return i &lt; 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i];
<a name="line534"></a>};
<a name="line535"></a>
<a name="line536"></a>
<a name="line537"></a>/**
<a name="line538"></a> * Search an array (in reverse order) for the last element that satisfies a
<a name="line539"></a> * given condition and return its index.
<a name="line540"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line541"></a> *     like object over which to iterate.
<a name="line542"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call
<a name="line543"></a> *     for every element. This function
<a name="line544"></a> *     takes 3 arguments (the element, the index and the array) and should
<a name="line545"></a> *     return a boolean.
<a name="line546"></a> * @param {Object=} opt_obj An optional &quot;this&quot; context for the function.
<a name="line547"></a> * @return {number} The index of the last array element that passes the test,
<a name="line548"></a> *     or -1 if no element is found.
<a name="line549"></a> * @template T,S
<a name="line550"></a> */
<a name="line551"></a>goog.array.findIndexRight = function(arr, f, opt_obj) {
<a name="line552"></a>  var l = arr.length;  // must be fixed during loop... see docs
<a name="line553"></a>  var arr2 = goog.isString(arr) ? arr.split(&#39;&#39;) : arr;
<a name="line554"></a>  for (var i = l - 1; i &gt;= 0; i--) {
<a name="line555"></a>    if (i in arr2 &amp;&amp; f.call(opt_obj, arr2[i], i, arr)) {
<a name="line556"></a>      return i;
<a name="line557"></a>    }
<a name="line558"></a>  }
<a name="line559"></a>  return -1;
<a name="line560"></a>};
<a name="line561"></a>
<a name="line562"></a>
<a name="line563"></a>/**
<a name="line564"></a> * Whether the array contains the given object.
<a name="line565"></a> * @param {goog.array.ArrayLike} arr The array to test for the presence of the
<a name="line566"></a> *     element.
<a name="line567"></a> * @param {*} obj The object for which to test.
<a name="line568"></a> * @return {boolean} true if obj is present.
<a name="line569"></a> */
<a name="line570"></a>goog.array.contains = function(arr, obj) {
<a name="line571"></a>  return goog.array.indexOf(arr, obj) &gt;= 0;
<a name="line572"></a>};
<a name="line573"></a>
<a name="line574"></a>
<a name="line575"></a>/**
<a name="line576"></a> * Whether the array is empty.
<a name="line577"></a> * @param {goog.array.ArrayLike} arr The array to test.
<a name="line578"></a> * @return {boolean} true if empty.
<a name="line579"></a> */
<a name="line580"></a>goog.array.isEmpty = function(arr) {
<a name="line581"></a>  return arr.length == 0;
<a name="line582"></a>};
<a name="line583"></a>
<a name="line584"></a>
<a name="line585"></a>/**
<a name="line586"></a> * Clears the array.
<a name="line587"></a> * @param {goog.array.ArrayLike} arr Array or array like object to clear.
<a name="line588"></a> */
<a name="line589"></a>goog.array.clear = function(arr) {
<a name="line590"></a>  // For non real arrays we don&#39;t have the magic length so we delete the
<a name="line591"></a>  // indices.
<a name="line592"></a>  if (!goog.isArray(arr)) {
<a name="line593"></a>    for (var i = arr.length - 1; i &gt;= 0; i--) {
<a name="line594"></a>      delete arr[i];
<a name="line595"></a>    }
<a name="line596"></a>  }
<a name="line597"></a>  arr.length = 0;
<a name="line598"></a>};
<a name="line599"></a>
<a name="line600"></a>
<a name="line601"></a>/**
<a name="line602"></a> * Pushes an item into an array, if it&#39;s not already in the array.
<a name="line603"></a> * @param {Array.&lt;T&gt;} arr Array into which to insert the item.
<a name="line604"></a> * @param {T} obj Value to add.
<a name="line605"></a> * @template T
<a name="line606"></a> */
<a name="line607"></a>goog.array.insert = function(arr, obj) {
<a name="line608"></a>  if (!goog.array.contains(arr, obj)) {
<a name="line609"></a>    arr.push(obj);
<a name="line610"></a>  }
<a name="line611"></a>};
<a name="line612"></a>
<a name="line613"></a>
<a name="line614"></a>/**
<a name="line615"></a> * Inserts an object at the given index of the array.
<a name="line616"></a> * @param {goog.array.ArrayLike} arr The array to modify.
<a name="line617"></a> * @param {*} obj The object to insert.
<a name="line618"></a> * @param {number=} opt_i The index at which to insert the object. If omitted,
<a name="line619"></a> *      treated as 0. A negative index is counted from the end of the array.
<a name="line620"></a> */
<a name="line621"></a>goog.array.insertAt = function(arr, obj, opt_i) {
<a name="line622"></a>  goog.array.splice(arr, opt_i, 0, obj);
<a name="line623"></a>};
<a name="line624"></a>
<a name="line625"></a>
<a name="line626"></a>/**
<a name="line627"></a> * Inserts at the given index of the array, all elements of another array.
<a name="line628"></a> * @param {goog.array.ArrayLike} arr The array to modify.
<a name="line629"></a> * @param {goog.array.ArrayLike} elementsToAdd The array of elements to add.
<a name="line630"></a> * @param {number=} opt_i The index at which to insert the object. If omitted,
<a name="line631"></a> *      treated as 0. A negative index is counted from the end of the array.
<a name="line632"></a> */
<a name="line633"></a>goog.array.insertArrayAt = function(arr, elementsToAdd, opt_i) {
<a name="line634"></a>  goog.partial(goog.array.splice, arr, opt_i, 0).apply(null, elementsToAdd);
<a name="line635"></a>};
<a name="line636"></a>
<a name="line637"></a>
<a name="line638"></a>/**
<a name="line639"></a> * Inserts an object into an array before a specified object.
<a name="line640"></a> * @param {Array.&lt;T&gt;} arr The array to modify.
<a name="line641"></a> * @param {T} obj The object to insert.
<a name="line642"></a> * @param {T=} opt_obj2 The object before which obj should be inserted. If obj2
<a name="line643"></a> *     is omitted or not found, obj is inserted at the end of the array.
<a name="line644"></a> * @template T
<a name="line645"></a> */
<a name="line646"></a>goog.array.insertBefore = function(arr, obj, opt_obj2) {
<a name="line647"></a>  var i;
<a name="line648"></a>  if (arguments.length == 2 || (i = goog.array.indexOf(arr, opt_obj2)) &lt; 0) {
<a name="line649"></a>    arr.push(obj);
<a name="line650"></a>  } else {
<a name="line651"></a>    goog.array.insertAt(arr, obj, i);
<a name="line652"></a>  }
<a name="line653"></a>};
<a name="line654"></a>
<a name="line655"></a>
<a name="line656"></a>/**
<a name="line657"></a> * Removes the first occurrence of a particular value from an array.
<a name="line658"></a> * @param {goog.array.ArrayLike} arr Array from which to remove value.
<a name="line659"></a> * @param {*} obj Object to remove.
<a name="line660"></a> * @return {boolean} True if an element was removed.
<a name="line661"></a> */
<a name="line662"></a>goog.array.remove = function(arr, obj) {
<a name="line663"></a>  var i = goog.array.indexOf(arr, obj);
<a name="line664"></a>  var rv;
<a name="line665"></a>  if ((rv = i &gt;= 0)) {
<a name="line666"></a>    goog.array.removeAt(arr, i);
<a name="line667"></a>  }
<a name="line668"></a>  return rv;
<a name="line669"></a>};
<a name="line670"></a>
<a name="line671"></a>
<a name="line672"></a>/**
<a name="line673"></a> * Removes from an array the element at index i
<a name="line674"></a> * @param {goog.array.ArrayLike} arr Array or array like object from which to
<a name="line675"></a> *     remove value.
<a name="line676"></a> * @param {number} i The index to remove.
<a name="line677"></a> * @return {boolean} True if an element was removed.
<a name="line678"></a> */
<a name="line679"></a>goog.array.removeAt = function(arr, i) {
<a name="line680"></a>  goog.asserts.assert(arr.length != null);
<a name="line681"></a>
<a name="line682"></a>  // use generic form of splice
<a name="line683"></a>  // splice returns the removed items and if successful the length of that
<a name="line684"></a>  // will be 1
<a name="line685"></a>  return goog.array.ARRAY_PROTOTYPE_.splice.call(arr, i, 1).length == 1;
<a name="line686"></a>};
<a name="line687"></a>
<a name="line688"></a>
<a name="line689"></a>/**
<a name="line690"></a> * Removes the first value that satisfies the given condition.
<a name="line691"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array
<a name="line692"></a> *     like object over which to iterate.
<a name="line693"></a> * @param {?function(this:S, T, number, ?) : boolean} f The function to call
<a name="line694"></a> *     for every element. This function
<a name="line695"></a> *     takes 3 arguments (the element, the index and the array) and should
<a name="line696"></a> *     return a boolean.
<a name="line697"></a> * @param {S=} opt_obj An optional &quot;this&quot; context for the function.
<a name="line698"></a> * @return {boolean} True if an element was removed.
<a name="line699"></a> * @template T,S
<a name="line700"></a> */
<a name="line701"></a>goog.array.removeIf = function(arr, f, opt_obj) {
<a name="line702"></a>  var i = goog.array.findIndex(arr, f, opt_obj);
<a name="line703"></a>  if (i &gt;= 0) {
<a name="line704"></a>    goog.array.removeAt(arr, i);
<a name="line705"></a>    return true;
<a name="line706"></a>  }
<a name="line707"></a>  return false;
<a name="line708"></a>};
<a name="line709"></a>
<a name="line710"></a>
<a name="line711"></a>/**
<a name="line712"></a> * Returns a new array that is the result of joining the arguments.  If arrays
<a name="line713"></a> * are passed then their items are added, however, if non-arrays are passed they
<a name="line714"></a> * will be added to the return array as is.
<a name="line715"></a> *
<a name="line716"></a> * Note that ArrayLike objects will be added as is, rather than having their
<a name="line717"></a> * items added.
<a name="line718"></a> *
<a name="line719"></a> * goog.array.concat([1, 2], [3, 4]) -&gt; [1, 2, 3, 4]
<a name="line720"></a> * goog.array.concat(0, [1, 2]) -&gt; [0, 1, 2]
<a name="line721"></a> * goog.array.concat([1, 2], null) -&gt; [1, 2, null]
<a name="line722"></a> *
<a name="line723"></a> * There is bug in all current versions of IE (6, 7 and 8) where arrays created
<a name="line724"></a> * in an iframe become corrupted soon (not immediately) after the iframe is
<a name="line725"></a> * destroyed. This is common if loading data via goog.net.IframeIo, for example.
<a name="line726"></a> * This corruption only affects the concat method which will start throwing
<a name="line727"></a> * Catastrophic Errors (#-2147418113).
<a name="line728"></a> *
<a name="line729"></a> * See http://endoflow.com/scratch/corrupted-arrays.html for a test case.
<a name="line730"></a> *
<a name="line731"></a> * Internally goog.array should use this, so that all methods will continue to
<a name="line732"></a> * work on these broken array objects.
<a name="line733"></a> *
<a name="line734"></a> * @param {...*} var_args Items to concatenate.  Arrays will have each item
<a name="line735"></a> *     added, while primitives and objects will be added as is.
<a name="line736"></a> * @return {!Array} The new resultant array.
<a name="line737"></a> */
<a name="line738"></a>goog.array.concat = function(var_args) {
<a name="line739"></a>  return goog.array.ARRAY_PROTOTYPE_.concat.apply(
<a name="line740"></a>      goog.array.ARRAY_PROTOTYPE_, arguments);
<a name="line741"></a>};
<a name="line742"></a>
<a name="line743"></a>
<a name="line744"></a>/**
<a name="line745"></a> * Converts an object to an array.
<a name="line746"></a> * @param {goog.array.ArrayLike} object  The object to convert to an array.
<a name="line747"></a> * @return {!Array} The object converted into an array. If object has a
<a name="line748"></a> *     length property, every property indexed with a non-negative number
<a name="line749"></a> *     less than length will be included in the result. If object does not
<a name="line750"></a> *     have a length property, an empty array will be returned.
<a name="line751"></a> */
<a name="line752"></a>goog.array.toArray = function(object) {
<a name="line753"></a>  var length = object.length;
<a name="line754"></a>
<a name="line755"></a>  // If length is not a number the following it false. This case is kept for
<a name="line756"></a>  // backwards compatibility since there are callers that pass objects that are
<a name="line757"></a>  // not array like.
<a name="line758"></a>  if (length &gt; 0) {
<a name="line759"></a>    var rv = new Array(length);
<a name="line760"></a>    for (var i = 0; i &lt; length; i++) {
<a name="line761"></a>      rv[i] = object[i];
<a name="line762"></a>    }
<a name="line763"></a>    return rv;
<a name="line764"></a>  }
<a name="line765"></a>  return [];
<a name="line766"></a>};
<a name="line767"></a>
<a name="line768"></a>
<a name="line769"></a>/**
<a name="line770"></a> * Does a shallow copy of an array.
<a name="line771"></a> * @param {goog.array.ArrayLike} arr  Array or array-like object to clone.
<a name="line772"></a> * @return {!Array} Clone of the input array.
<a name="line773"></a> */
<a name="line774"></a>goog.array.clone = goog.array.toArray;
<a name="line775"></a>
<a name="line776"></a>
<a name="line777"></a>/**
<a name="line778"></a> * Extends an array with another array, element, or &quot;array like&quot; object.
<a name="line779"></a> * This function operates &#39;in-place&#39;, it does not create a new Array.
<a name="line780"></a> *
<a name="line781"></a> * Example:
<a name="line782"></a> * var a = [];
<a name="line783"></a> * goog.array.extend(a, [0, 1]);
<a name="line784"></a> * a; // [0, 1]
<a name="line785"></a> * goog.array.extend(a, 2);
<a name="line786"></a> * a; // [0, 1, 2]
<a name="line787"></a> *
<a name="line788"></a> * @param {Array} arr1  The array to modify.
<a name="line789"></a> * @param {...*} var_args The elements or arrays of elements to add to arr1.
<a name="line790"></a> */
<a name="line791"></a>goog.array.extend = function(arr1, var_args) {
<a name="line792"></a>  for (var i = 1; i &lt; arguments.length; i++) {
<a name="line793"></a>    var arr2 = arguments[i];
<a name="line794"></a>    // If we have an Array or an Arguments object we can just call push
<a name="line795"></a>    // directly.
<a name="line796"></a>    var isArrayLike;
<a name="line797"></a>    if (goog.isArray(arr2) ||
<a name="line798"></a>        // Detect Arguments. ES5 says that the [[Class]] of an Arguments object
<a name="line799"></a>        // is &quot;Arguments&quot; but only V8 and JSC/Safari gets this right. We instead
<a name="line800"></a>        // detect Arguments by checking for array like and presence of &quot;callee&quot;.
<a name="line801"></a>        (isArrayLike = goog.isArrayLike(arr2)) &amp;&amp;
<a name="line802"></a>            // The getter for callee throws an exception in strict mode
<a name="line803"></a>            // according to section 10.6 in ES5 so check for presence instead.
<a name="line804"></a>            Object.prototype.hasOwnProperty.call(arr2, &#39;callee&#39;)) {
<a name="line805"></a>      arr1.push.apply(arr1, arr2);
<a name="line806"></a>    } else if (isArrayLike) {
<a name="line807"></a>      // Otherwise loop over arr2 to prevent copying the object.
<a name="line808"></a>      var len1 = arr1.length;
<a name="line809"></a>      var len2 = arr2.length;
<a name="line810"></a>      for (var j = 0; j &lt; len2; j++) {
<a name="line811"></a>        arr1[len1 + j] = arr2[j];
<a name="line812"></a>      }
<a name="line813"></a>    } else {
<a name="line814"></a>      arr1.push(arr2);
<a name="line815"></a>    }
<a name="line816"></a>  }
<a name="line817"></a>};
<a name="line818"></a>
<a name="line819"></a>
<a name="line820"></a>/**
<a name="line821"></a> * Adds or removes elements from an array. This is a generic version of Array
<a name="line822"></a> * splice. This means that it might work on other objects similar to arrays,
<a name="line823"></a> * such as the arguments object.
<a name="line824"></a> *
<a name="line825"></a> * @param {goog.array.ArrayLike} arr The array to modify.
<a name="line826"></a> * @param {number|undefined} index The index at which to start changing the
<a name="line827"></a> *     array. If not defined, treated as 0.
<a name="line828"></a> * @param {number} howMany How many elements to remove (0 means no removal. A
<a name="line829"></a> *     value below 0 is treated as zero and so is any other non number. Numbers
<a name="line830"></a> *     are floored).
<a name="line831"></a> * @param {...*} var_args Optional, additional elements to insert into the
<a name="line832"></a> *     array.
<a name="line833"></a> * @return {!Array} the removed elements.
<a name="line834"></a> */
<a name="line835"></a>goog.array.splice = function(arr, index, howMany, var_args) {
<a name="line836"></a>  goog.asserts.assert(arr.length != null);
<a name="line837"></a>
<a name="line838"></a>  return goog.array.ARRAY_PROTOTYPE_.splice.apply(
<a name="line839"></a>      arr, goog.array.slice(arguments, 1));
<a name="line840"></a>};
<a name="line841"></a>
<a name="line842"></a>
<a name="line843"></a>/**
<a name="line844"></a> * Returns a new array from a segment of an array. This is a generic version of
<a name="line845"></a> * Array slice. This means that it might work on other objects similar to
<a name="line846"></a> * arrays, such as the arguments object.
<a name="line847"></a> *
<a name="line848"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr The array from
<a name="line849"></a> * which to copy a segment.
<a name="line850"></a> * @param {number} start The index of the first element to copy.
<a name="line851"></a> * @param {number=} opt_end The index after the last element to copy.
<a name="line852"></a> * @return {!Array.&lt;T&gt;} A new array containing the specified segment of the
<a name="line853"></a> *     original array.
<a name="line854"></a> * @template T
<a name="line855"></a> */
<a name="line856"></a>goog.array.slice = function(arr, start, opt_end) {
<a name="line857"></a>  goog.asserts.assert(arr.length != null);
<a name="line858"></a>
<a name="line859"></a>  // passing 1 arg to slice is not the same as passing 2 where the second is
<a name="line860"></a>  // null or undefined (in that case the second argument is treated as 0).
<a name="line861"></a>  // we could use slice on the arguments object and then use apply instead of
<a name="line862"></a>  // testing the length
<a name="line863"></a>  if (arguments.length &lt;= 2) {
<a name="line864"></a>    return goog.array.ARRAY_PROTOTYPE_.slice.call(arr, start);
<a name="line865"></a>  } else {
<a name="line866"></a>    return goog.array.ARRAY_PROTOTYPE_.slice.call(arr, start, opt_end);
<a name="line867"></a>  }
<a name="line868"></a>};
<a name="line869"></a>
<a name="line870"></a>
<a name="line871"></a>/**
<a name="line872"></a> * Removes all duplicates from an array (retaining only the first
<a name="line873"></a> * occurrence of each array element).  This function modifies the
<a name="line874"></a> * array in place and doesn&#39;t change the order of the non-duplicate items.
<a name="line875"></a> *
<a name="line876"></a> * For objects, duplicates are identified as having the same unique ID as
<a name="line877"></a> * defined by {@link goog.getUid}.
<a name="line878"></a> *
<a name="line879"></a> * Runtime: N,
<a name="line880"></a> * Worstcase space: 2N (no dupes)
<a name="line881"></a> *
<a name="line882"></a> * @param {goog.array.ArrayLike} arr The array from which to remove duplicates.
<a name="line883"></a> * @param {Array=} opt_rv An optional array in which to return the results,
<a name="line884"></a> *     instead of performing the removal inplace.  If specified, the original
<a name="line885"></a> *     array will remain unchanged.
<a name="line886"></a> */
<a name="line887"></a>goog.array.removeDuplicates = function(arr, opt_rv) {
<a name="line888"></a>  var returnArray = opt_rv || arr;
<a name="line889"></a>
<a name="line890"></a>  var seen = {}, cursorInsert = 0, cursorRead = 0;
<a name="line891"></a>  while (cursorRead &lt; arr.length) {
<a name="line892"></a>    var current = arr[cursorRead++];
<a name="line893"></a>
<a name="line894"></a>    // Prefix each type with a single character representing the type to
<a name="line895"></a>    // prevent conflicting keys (e.g. true and &#39;true&#39;).
<a name="line896"></a>    var key = goog.isObject(current) ?
<a name="line897"></a>        &#39;o&#39; + goog.getUid(current) :
<a name="line898"></a>        (typeof current).charAt(0) + current;
<a name="line899"></a>
<a name="line900"></a>    if (!Object.prototype.hasOwnProperty.call(seen, key)) {
<a name="line901"></a>      seen[key] = true;
<a name="line902"></a>      returnArray[cursorInsert++] = current;
<a name="line903"></a>    }
<a name="line904"></a>  }
<a name="line905"></a>  returnArray.length = cursorInsert;
<a name="line906"></a>};
<a name="line907"></a>
<a name="line908"></a>
<a name="line909"></a>/**
<a name="line910"></a> * Searches the specified array for the specified target using the binary
<a name="line911"></a> * search algorithm.  If no opt_compareFn is specified, elements are compared
<a name="line912"></a> * using &lt;code&gt;goog.array.defaultCompare&lt;/code&gt;, which compares the elements
<a name="line913"></a> * using the built in &lt; and &gt; operators.  This will produce the expected
<a name="line914"></a> * behavior for homogeneous arrays of String(s) and Number(s). The array
<a name="line915"></a> * specified &lt;b&gt;must&lt;/b&gt; be sorted in ascending order (as defined by the
<a name="line916"></a> * comparison function).  If the array is not sorted, results are undefined.
<a name="line917"></a> * If the array contains multiple instances of the specified target value, any
<a name="line918"></a> * of these instances may be found.
<a name="line919"></a> *
<a name="line920"></a> * Runtime: O(log n)
<a name="line921"></a> *
<a name="line922"></a> * @param {goog.array.ArrayLike} arr The array to be searched.
<a name="line923"></a> * @param {*} target The sought value.
<a name="line924"></a> * @param {Function=} opt_compareFn Optional comparison function by which the
<a name="line925"></a> *     array is ordered. Should take 2 arguments to compare, and return a
<a name="line926"></a> *     negative number, zero, or a positive number depending on whether the
<a name="line927"></a> *     first argument is less than, equal to, or greater than the second.
<a name="line928"></a> * @return {number} Lowest index of the target value if found, otherwise
<a name="line929"></a> *     (-(insertion point) - 1). The insertion point is where the value should
<a name="line930"></a> *     be inserted into arr to preserve the sorted property.  Return value &gt;= 0
<a name="line931"></a> *     iff target is found.
<a name="line932"></a> */
<a name="line933"></a>goog.array.binarySearch = function(arr, target, opt_compareFn) {
<a name="line934"></a>  return goog.array.binarySearch_(arr,
<a name="line935"></a>      opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */,
<a name="line936"></a>      target);
<a name="line937"></a>};
<a name="line938"></a>
<a name="line939"></a>
<a name="line940"></a>/**
<a name="line941"></a> * Selects an index in the specified array using the binary search algorithm.
<a name="line942"></a> * The evaluator receives an element and determines whether the desired index
<a name="line943"></a> * is before, at, or after it.  The evaluator must be consistent (formally,
<a name="line944"></a> * goog.array.map(goog.array.map(arr, evaluator, opt_obj), goog.math.sign)
<a name="line945"></a> * must be monotonically non-increasing).
<a name="line946"></a> *
<a name="line947"></a> * Runtime: O(log n)
<a name="line948"></a> *
<a name="line949"></a> * @param {goog.array.ArrayLike} arr The array to be searched.
<a name="line950"></a> * @param {Function} evaluator Evaluator function that receives 3 arguments
<a name="line951"></a> *     (the element, the index and the array). Should return a negative number,
<a name="line952"></a> *     zero, or a positive number depending on whether the desired index is
<a name="line953"></a> *     before, at, or after the element passed to it.
<a name="line954"></a> * @param {Object=} opt_obj The object to be used as the value of &#39;this&#39;
<a name="line955"></a> *     within evaluator.
<a name="line956"></a> * @return {number} Index of the leftmost element matched by the evaluator, if
<a name="line957"></a> *     such exists; otherwise (-(insertion point) - 1). The insertion point is
<a name="line958"></a> *     the index of the first element for which the evaluator returns negative,
<a name="line959"></a> *     or arr.length if no such element exists. The return value is non-negative
<a name="line960"></a> *     iff a match is found.
<a name="line961"></a> */
<a name="line962"></a>goog.array.binarySelect = function(arr, evaluator, opt_obj) {
<a name="line963"></a>  return goog.array.binarySearch_(arr, evaluator, true /* isEvaluator */,
<a name="line964"></a>      undefined /* opt_target */, opt_obj);
<a name="line965"></a>};
<a name="line966"></a>
<a name="line967"></a>
<a name="line968"></a>/**
<a name="line969"></a> * Implementation of a binary search algorithm which knows how to use both
<a name="line970"></a> * comparison functions and evaluators. If an evaluator is provided, will call
<a name="line971"></a> * the evaluator with the given optional data object, conforming to the
<a name="line972"></a> * interface defined in binarySelect. Otherwise, if a comparison function is
<a name="line973"></a> * provided, will call the comparison function against the given data object.
<a name="line974"></a> *
<a name="line975"></a> * This implementation purposefully does not use goog.bind or goog.partial for
<a name="line976"></a> * performance reasons.
<a name="line977"></a> *
<a name="line978"></a> * Runtime: O(log n)
<a name="line979"></a> *
<a name="line980"></a> * @param {goog.array.ArrayLike} arr The array to be searched.
<a name="line981"></a> * @param {Function} compareFn Either an evaluator or a comparison function,
<a name="line982"></a> *     as defined by binarySearch and binarySelect above.
<a name="line983"></a> * @param {boolean} isEvaluator Whether the function is an evaluator or a
<a name="line984"></a> *     comparison function.
<a name="line985"></a> * @param {*=} opt_target If the function is a comparison function, then this is
<a name="line986"></a> *     the target to binary search for.
<a name="line987"></a> * @param {Object=} opt_selfObj If the function is an evaluator, this is an
<a name="line988"></a>  *    optional this object for the evaluator.
<a name="line989"></a> * @return {number} Lowest index of the target value if found, otherwise
<a name="line990"></a> *     (-(insertion point) - 1). The insertion point is where the value should
<a name="line991"></a> *     be inserted into arr to preserve the sorted property.  Return value &gt;= 0
<a name="line992"></a> *     iff target is found.
<a name="line993"></a> * @private
<a name="line994"></a> */
<a name="line995"></a>goog.array.binarySearch_ = function(arr, compareFn, isEvaluator, opt_target,
<a name="line996"></a>    opt_selfObj) {
<a name="line997"></a>  var left = 0;  // inclusive
<a name="line998"></a>  var right = arr.length;  // exclusive
<a name="line999"></a>  var found;
<a name="line1000"></a>  while (left &lt; right) {
<a name="line1001"></a>    var middle = (left + right) &gt;&gt; 1;
<a name="line1002"></a>    var compareResult;
<a name="line1003"></a>    if (isEvaluator) {
<a name="line1004"></a>      compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr);
<a name="line1005"></a>    } else {
<a name="line1006"></a>      compareResult = compareFn(opt_target, arr[middle]);
<a name="line1007"></a>    }
<a name="line1008"></a>    if (compareResult &gt; 0) {
<a name="line1009"></a>      left = middle + 1;
<a name="line1010"></a>    } else {
<a name="line1011"></a>      right = middle;
<a name="line1012"></a>      // We are looking for the lowest index so we can&#39;t return immediately.
<a name="line1013"></a>      found = !compareResult;
<a name="line1014"></a>    }
<a name="line1015"></a>  }
<a name="line1016"></a>  // left is the index if found, or the insertion point otherwise.
<a name="line1017"></a>  // ~left is a shorthand for -left - 1.
<a name="line1018"></a>  return found ? left : ~left;
<a name="line1019"></a>};
<a name="line1020"></a>
<a name="line1021"></a>
<a name="line1022"></a>/**
<a name="line1023"></a> * Sorts the specified array into ascending order.  If no opt_compareFn is
<a name="line1024"></a> * specified, elements are compared using
<a name="line1025"></a> * &lt;code&gt;goog.array.defaultCompare&lt;/code&gt;, which compares the elements using
<a name="line1026"></a> * the built in &lt; and &gt; operators.  This will produce the expected behavior
<a name="line1027"></a> * for homogeneous arrays of String(s) and Number(s), unlike the native sort,
<a name="line1028"></a> * but will give unpredictable results for heterogenous lists of strings and
<a name="line1029"></a> * numbers with different numbers of digits.
<a name="line1030"></a> *
<a name="line1031"></a> * This sort is not guaranteed to be stable.
<a name="line1032"></a> *
<a name="line1033"></a> * Runtime: Same as &lt;code&gt;Array.prototype.sort&lt;/code&gt;
<a name="line1034"></a> *
<a name="line1035"></a> * @param {Array.&lt;T&gt;} arr The array to be sorted.
<a name="line1036"></a> * @param {?function(T,T):number=} opt_compareFn Optional comparison
<a name="line1037"></a> *     function by which the
<a name="line1038"></a> *     array is to be ordered. Should take 2 arguments to compare, and return a
<a name="line1039"></a> *     negative number, zero, or a positive number depending on whether the
<a name="line1040"></a> *     first argument is less than, equal to, or greater than the second.
<a name="line1041"></a> * @template T
<a name="line1042"></a> */
<a name="line1043"></a>goog.array.sort = function(arr, opt_compareFn) {
<a name="line1044"></a>  // TODO(arv): Update type annotation since null is not accepted.
<a name="line1045"></a>  goog.asserts.assert(arr.length != null);
<a name="line1046"></a>
<a name="line1047"></a>  goog.array.ARRAY_PROTOTYPE_.sort.call(
<a name="line1048"></a>      arr, opt_compareFn || goog.array.defaultCompare);
<a name="line1049"></a>};
<a name="line1050"></a>
<a name="line1051"></a>
<a name="line1052"></a>/**
<a name="line1053"></a> * Sorts the specified array into ascending order in a stable way.  If no
<a name="line1054"></a> * opt_compareFn is specified, elements are compared using
<a name="line1055"></a> * &lt;code&gt;goog.array.defaultCompare&lt;/code&gt;, which compares the elements using
<a name="line1056"></a> * the built in &lt; and &gt; operators.  This will produce the expected behavior
<a name="line1057"></a> * for homogeneous arrays of String(s) and Number(s).
<a name="line1058"></a> *
<a name="line1059"></a> * Runtime: Same as &lt;code&gt;Array.prototype.sort&lt;/code&gt;, plus an additional
<a name="line1060"></a> * O(n) overhead of copying the array twice.
<a name="line1061"></a> *
<a name="line1062"></a> * @param {Array.&lt;T&gt;} arr The array to be sorted.
<a name="line1063"></a> * @param {?function(T, T): number=} opt_compareFn Optional comparison function
<a name="line1064"></a> *     by which the array is to be ordered. Should take 2 arguments to compare,
<a name="line1065"></a> *     and return a negative number, zero, or a positive number depending on
<a name="line1066"></a> *     whether the first argument is less than, equal to, or greater than the
<a name="line1067"></a> *     second.
<a name="line1068"></a> * @template T
<a name="line1069"></a> */
<a name="line1070"></a>goog.array.stableSort = function(arr, opt_compareFn) {
<a name="line1071"></a>  for (var i = 0; i &lt; arr.length; i++) {
<a name="line1072"></a>    arr[i] = {index: i, value: arr[i]};
<a name="line1073"></a>  }
<a name="line1074"></a>  var valueCompareFn = opt_compareFn || goog.array.defaultCompare;
<a name="line1075"></a>  function stableCompareFn(obj1, obj2) {
<a name="line1076"></a>    return valueCompareFn(obj1.value, obj2.value) || obj1.index - obj2.index;
<a name="line1077"></a>  };
<a name="line1078"></a>  goog.array.sort(arr, stableCompareFn);
<a name="line1079"></a>  for (var i = 0; i &lt; arr.length; i++) {
<a name="line1080"></a>    arr[i] = arr[i].value;
<a name="line1081"></a>  }
<a name="line1082"></a>};
<a name="line1083"></a>
<a name="line1084"></a>
<a name="line1085"></a>/**
<a name="line1086"></a> * Sorts an array of objects by the specified object key and compare
<a name="line1087"></a> * function. If no compare function is provided, the key values are
<a name="line1088"></a> * compared in ascending order using &lt;code&gt;goog.array.defaultCompare&lt;/code&gt;.
<a name="line1089"></a> * This won&#39;t work for keys that get renamed by the compiler. So use
<a name="line1090"></a> * {&#39;foo&#39;: 1, &#39;bar&#39;: 2} rather than {foo: 1, bar: 2}.
<a name="line1091"></a> * @param {Array.&lt;Object&gt;} arr An array of objects to sort.
<a name="line1092"></a> * @param {string} key The object key to sort by.
<a name="line1093"></a> * @param {Function=} opt_compareFn The function to use to compare key
<a name="line1094"></a> *     values.
<a name="line1095"></a> */
<a name="line1096"></a>goog.array.sortObjectsByKey = function(arr, key, opt_compareFn) {
<a name="line1097"></a>  var compare = opt_compareFn || goog.array.defaultCompare;
<a name="line1098"></a>  goog.array.sort(arr, function(a, b) {
<a name="line1099"></a>    return compare(a[key], b[key]);
<a name="line1100"></a>  });
<a name="line1101"></a>};
<a name="line1102"></a>
<a name="line1103"></a>
<a name="line1104"></a>/**
<a name="line1105"></a> * Tells if the array is sorted.
<a name="line1106"></a> * @param {!Array.&lt;T&gt;} arr The array.
<a name="line1107"></a> * @param {?function(T,T):number=} opt_compareFn Function to compare the
<a name="line1108"></a> *     array elements.
<a name="line1109"></a> *     Should take 2 arguments to compare, and return a negative number, zero,
<a name="line1110"></a> *     or a positive number depending on whether the first argument is less
<a name="line1111"></a> *     than, equal to, or greater than the second.
<a name="line1112"></a> * @param {boolean=} opt_strict If true no equal elements are allowed.
<a name="line1113"></a> * @return {boolean} Whether the array is sorted.
<a name="line1114"></a> * @template T
<a name="line1115"></a> */
<a name="line1116"></a>goog.array.isSorted = function(arr, opt_compareFn, opt_strict) {
<a name="line1117"></a>  var compare = opt_compareFn || goog.array.defaultCompare;
<a name="line1118"></a>  for (var i = 1; i &lt; arr.length; i++) {
<a name="line1119"></a>    var compareResult = compare(arr[i - 1], arr[i]);
<a name="line1120"></a>    if (compareResult &gt; 0 || compareResult == 0 &amp;&amp; opt_strict) {
<a name="line1121"></a>      return false;
<a name="line1122"></a>    }
<a name="line1123"></a>  }
<a name="line1124"></a>  return true;
<a name="line1125"></a>};
<a name="line1126"></a>
<a name="line1127"></a>
<a name="line1128"></a>/**
<a name="line1129"></a> * Compares two arrays for equality. Two arrays are considered equal if they
<a name="line1130"></a> * have the same length and their corresponding elements are equal according to
<a name="line1131"></a> * the comparison function.
<a name="line1132"></a> *
<a name="line1133"></a> * @param {goog.array.ArrayLike} arr1 The first array to compare.
<a name="line1134"></a> * @param {goog.array.ArrayLike} arr2 The second array to compare.
<a name="line1135"></a> * @param {Function=} opt_equalsFn Optional comparison function.
<a name="line1136"></a> *     Should take 2 arguments to compare, and return true if the arguments
<a name="line1137"></a> *     are equal. Defaults to {@link goog.array.defaultCompareEquality} which
<a name="line1138"></a> *     compares the elements using the built-in &#39;===&#39; operator.
<a name="line1139"></a> * @return {boolean} Whether the two arrays are equal.
<a name="line1140"></a> */
<a name="line1141"></a>goog.array.equals = function(arr1, arr2, opt_equalsFn) {
<a name="line1142"></a>  if (!goog.isArrayLike(arr1) || !goog.isArrayLike(arr2) ||
<a name="line1143"></a>      arr1.length != arr2.length) {
<a name="line1144"></a>    return false;
<a name="line1145"></a>  }
<a name="line1146"></a>  var l = arr1.length;
<a name="line1147"></a>  var equalsFn = opt_equalsFn || goog.array.defaultCompareEquality;
<a name="line1148"></a>  for (var i = 0; i &lt; l; i++) {
<a name="line1149"></a>    if (!equalsFn(arr1[i], arr2[i])) {
<a name="line1150"></a>      return false;
<a name="line1151"></a>    }
<a name="line1152"></a>  }
<a name="line1153"></a>  return true;
<a name="line1154"></a>};
<a name="line1155"></a>
<a name="line1156"></a>
<a name="line1157"></a>/**
<a name="line1158"></a> * @deprecated Use {@link goog.array.equals}.
<a name="line1159"></a> * @param {goog.array.ArrayLike} arr1 See {@link goog.array.equals}.
<a name="line1160"></a> * @param {goog.array.ArrayLike} arr2 See {@link goog.array.equals}.
<a name="line1161"></a> * @param {Function=} opt_equalsFn See {@link goog.array.equals}.
<a name="line1162"></a> * @return {boolean} See {@link goog.array.equals}.
<a name="line1163"></a> */
<a name="line1164"></a>goog.array.compare = function(arr1, arr2, opt_equalsFn) {
<a name="line1165"></a>  return goog.array.equals(arr1, arr2, opt_equalsFn);
<a name="line1166"></a>};
<a name="line1167"></a>
<a name="line1168"></a>
<a name="line1169"></a>/**
<a name="line1170"></a> * 3-way array compare function.
<a name="line1171"></a> * @param {!goog.array.ArrayLike} arr1 The first array to compare.
<a name="line1172"></a> * @param {!goog.array.ArrayLike} arr2 The second array to compare.
<a name="line1173"></a> * @param {?function(?, ?): number=} opt_compareFn Optional comparison function
<a name="line1174"></a> *     by which the array is to be ordered. Should take 2 arguments to compare,
<a name="line1175"></a> *     and return a negative number, zero, or a positive number depending on
<a name="line1176"></a> *     whether the first argument is less than, equal to, or greater than the
<a name="line1177"></a> *     second.
<a name="line1178"></a> * @return {number} Negative number, zero, or a positive number depending on
<a name="line1179"></a> *     whether the first argument is less than, equal to, or greater than the
<a name="line1180"></a> *     second.
<a name="line1181"></a> */
<a name="line1182"></a>goog.array.compare3 = function(arr1, arr2, opt_compareFn) {
<a name="line1183"></a>  var compare = opt_compareFn || goog.array.defaultCompare;
<a name="line1184"></a>  var l = Math.min(arr1.length, arr2.length);
<a name="line1185"></a>  for (var i = 0; i &lt; l; i++) {
<a name="line1186"></a>    var result = compare(arr1[i], arr2[i]);
<a name="line1187"></a>    if (result != 0) {
<a name="line1188"></a>      return result;
<a name="line1189"></a>    }
<a name="line1190"></a>  }
<a name="line1191"></a>  return goog.array.defaultCompare(arr1.length, arr2.length);
<a name="line1192"></a>};
<a name="line1193"></a>
<a name="line1194"></a>
<a name="line1195"></a>/**
<a name="line1196"></a> * Compares its two arguments for order, using the built in &lt; and &gt;
<a name="line1197"></a> * operators.
<a name="line1198"></a> * @param {*} a The first object to be compared.
<a name="line1199"></a> * @param {*} b The second object to be compared.
<a name="line1200"></a> * @return {number} A negative number, zero, or a positive number as the first
<a name="line1201"></a> *     argument is less than, equal to, or greater than the second.
<a name="line1202"></a> */
<a name="line1203"></a>goog.array.defaultCompare = function(a, b) {
<a name="line1204"></a>  return a &gt; b ? 1 : a &lt; b ? -1 : 0;
<a name="line1205"></a>};
<a name="line1206"></a>
<a name="line1207"></a>
<a name="line1208"></a>/**
<a name="line1209"></a> * Compares its two arguments for equality, using the built in === operator.
<a name="line1210"></a> * @param {*} a The first object to compare.
<a name="line1211"></a> * @param {*} b The second object to compare.
<a name="line1212"></a> * @return {boolean} True if the two arguments are equal, false otherwise.
<a name="line1213"></a> */
<a name="line1214"></a>goog.array.defaultCompareEquality = function(a, b) {
<a name="line1215"></a>  return a === b;
<a name="line1216"></a>};
<a name="line1217"></a>
<a name="line1218"></a>
<a name="line1219"></a>/**
<a name="line1220"></a> * Inserts a value into a sorted array. The array is not modified if the
<a name="line1221"></a> * value is already present.
<a name="line1222"></a> * @param {Array.&lt;T&gt;} array The array to modify.
<a name="line1223"></a> * @param {T} value The object to insert.
<a name="line1224"></a> * @param {?function(T,T):number=} opt_compareFn Optional comparison function by
<a name="line1225"></a> *     which the
<a name="line1226"></a> *     array is ordered. Should take 2 arguments to compare, and return a
<a name="line1227"></a> *     negative number, zero, or a positive number depending on whether the
<a name="line1228"></a> *     first argument is less than, equal to, or greater than the second.
<a name="line1229"></a> * @return {boolean} True if an element was inserted.
<a name="line1230"></a> * @template T
<a name="line1231"></a> */
<a name="line1232"></a>goog.array.binaryInsert = function(array, value, opt_compareFn) {
<a name="line1233"></a>  var index = goog.array.binarySearch(array, value, opt_compareFn);
<a name="line1234"></a>  if (index &lt; 0) {
<a name="line1235"></a>    goog.array.insertAt(array, value, -(index + 1));
<a name="line1236"></a>    return true;
<a name="line1237"></a>  }
<a name="line1238"></a>  return false;
<a name="line1239"></a>};
<a name="line1240"></a>
<a name="line1241"></a>
<a name="line1242"></a>/**
<a name="line1243"></a> * Removes a value from a sorted array.
<a name="line1244"></a> * @param {Array} array The array to modify.
<a name="line1245"></a> * @param {*} value The object to remove.
<a name="line1246"></a> * @param {Function=} opt_compareFn Optional comparison function by which the
<a name="line1247"></a> *     array is ordered. Should take 2 arguments to compare, and return a
<a name="line1248"></a> *     negative number, zero, or a positive number depending on whether the
<a name="line1249"></a> *     first argument is less than, equal to, or greater than the second.
<a name="line1250"></a> * @return {boolean} True if an element was removed.
<a name="line1251"></a> */
<a name="line1252"></a>goog.array.binaryRemove = function(array, value, opt_compareFn) {
<a name="line1253"></a>  var index = goog.array.binarySearch(array, value, opt_compareFn);
<a name="line1254"></a>  return (index &gt;= 0) ? goog.array.removeAt(array, index) : false;
<a name="line1255"></a>};
<a name="line1256"></a>
<a name="line1257"></a>
<a name="line1258"></a>/**
<a name="line1259"></a> * Splits an array into disjoint buckets according to a splitting function.
<a name="line1260"></a> * @param {Array.&lt;T&gt;} array The array.
<a name="line1261"></a> * @param {function(T,number,Array.&lt;T&gt;):?} sorter Function to call for every
<a name="line1262"></a> *     element.  This
<a name="line1263"></a> *     takes 3 arguments (the element, the index and the array) and must
<a name="line1264"></a> *     return a valid object key (a string, number, etc), or undefined, if
<a name="line1265"></a> *     that object should not be placed in a bucket.
<a name="line1266"></a> * @return {!Object} An object, with keys being all of the unique return values
<a name="line1267"></a> *     of sorter, and values being arrays containing the items for
<a name="line1268"></a> *     which the splitter returned that key.
<a name="line1269"></a> * @template T
<a name="line1270"></a> */
<a name="line1271"></a>goog.array.bucket = function(array, sorter) {
<a name="line1272"></a>  var buckets = {};
<a name="line1273"></a>
<a name="line1274"></a>  for (var i = 0; i &lt; array.length; i++) {
<a name="line1275"></a>    var value = array[i];
<a name="line1276"></a>    var key = sorter(value, i, array);
<a name="line1277"></a>    if (goog.isDef(key)) {
<a name="line1278"></a>      // Push the value to the right bucket, creating it if necessary.
<a name="line1279"></a>      var bucket = buckets[key] || (buckets[key] = []);
<a name="line1280"></a>      bucket.push(value);
<a name="line1281"></a>    }
<a name="line1282"></a>  }
<a name="line1283"></a>
<a name="line1284"></a>  return buckets;
<a name="line1285"></a>};
<a name="line1286"></a>
<a name="line1287"></a>
<a name="line1288"></a>/**
<a name="line1289"></a> * Creates a new object built from the provided array and the key-generation
<a name="line1290"></a> * function.
<a name="line1291"></a> * @param {Array.&lt;T&gt;|goog.array.ArrayLike} arr Array or array like object over
<a name="line1292"></a> *     which to iterate whose elements will be the values in the new object.
<a name="line1293"></a> * @param {?function(this:S, T, number, ?) : string} keyFunc The function to
<a name="line1294"></a> *     call for every element. This function takes 3 arguments (the element, the
<a name="line1295"></a> *     index and the array) and should return a string that will be used as the
<a name="line1296"></a> *     key for the element in the new object. If the function returns the same
<a name="line1297"></a> *     key for more than one element, the value for that key is
<a name="line1298"></a> *     implementation-defined.
<a name="line1299"></a> * @param {S=} opt_obj  The object to be used as the value of &#39;this&#39;
<a name="line1300"></a> *     within keyFunc.
<a name="line1301"></a> * @return {!Object.&lt;T&gt;} The new object.
<a name="line1302"></a> * @template T,S
<a name="line1303"></a> */
<a name="line1304"></a>goog.array.toObject = function(arr, keyFunc, opt_obj) {
<a name="line1305"></a>  var ret = {};
<a name="line1306"></a>  goog.array.forEach(arr, function(element, index) {
<a name="line1307"></a>    ret[keyFunc.call(opt_obj, element, index, arr)] = element;
<a name="line1308"></a>  });
<a name="line1309"></a>  return ret;
<a name="line1310"></a>};
<a name="line1311"></a>
<a name="line1312"></a>
<a name="line1313"></a>/**
<a name="line1314"></a> * Creates a range of numbers in an arithmetic progression.
<a name="line1315"></a> *
<a name="line1316"></a> * Range takes 1, 2, or 3 arguments:
<a name="line1317"></a> * &lt;pre&gt;
<a name="line1318"></a> * range(5) is the same as range(0, 5, 1) and produces [0, 1, 2, 3, 4]
<a name="line1319"></a> * range(2, 5) is the same as range(2, 5, 1) and produces [2, 3, 4]
<a name="line1320"></a> * range(-2, -5, -1) produces [-2, -3, -4]
<a name="line1321"></a> * range(-2, -5, 1) produces [], since stepping by 1 wouldn&#39;t ever reach -5.
<a name="line1322"></a> * &lt;/pre&gt;
<a name="line1323"></a> *
<a name="line1324"></a> * @param {number} startOrEnd The starting value of the range if an end argument
<a name="line1325"></a> *     is provided. Otherwise, the start value is 0, and this is the end value.
<a name="line1326"></a> * @param {number=} opt_end The optional end value of the range.
<a name="line1327"></a> * @param {number=} opt_step The step size between range values. Defaults to 1
<a name="line1328"></a> *     if opt_step is undefined or 0.
<a name="line1329"></a> * @return {!Array.&lt;number&gt;} An array of numbers for the requested range. May be
<a name="line1330"></a> *     an empty array if adding the step would not converge toward the end
<a name="line1331"></a> *     value.
<a name="line1332"></a> */
<a name="line1333"></a>goog.array.range = function(startOrEnd, opt_end, opt_step) {
<a name="line1334"></a>  var array = [];
<a name="line1335"></a>  var start = 0;
<a name="line1336"></a>  var end = startOrEnd;
<a name="line1337"></a>  var step = opt_step || 1;
<a name="line1338"></a>  if (opt_end !== undefined) {
<a name="line1339"></a>    start = startOrEnd;
<a name="line1340"></a>    end = opt_end;
<a name="line1341"></a>  }
<a name="line1342"></a>
<a name="line1343"></a>  if (step * (end - start) &lt; 0) {
<a name="line1344"></a>    // Sign mismatch: start + step will never reach the end value.
<a name="line1345"></a>    return [];
<a name="line1346"></a>  }
<a name="line1347"></a>
<a name="line1348"></a>  if (step &gt; 0) {
<a name="line1349"></a>    for (var i = start; i &lt; end; i += step) {
<a name="line1350"></a>      array.push(i);
<a name="line1351"></a>    }
<a name="line1352"></a>  } else {
<a name="line1353"></a>    for (var i = start; i &gt; end; i += step) {
<a name="line1354"></a>      array.push(i);
<a name="line1355"></a>    }
<a name="line1356"></a>  }
<a name="line1357"></a>  return array;
<a name="line1358"></a>};
<a name="line1359"></a>
<a name="line1360"></a>
<a name="line1361"></a>/**
<a name="line1362"></a> * Returns an array consisting of the given value repeated N times.
<a name="line1363"></a> *
<a name="line1364"></a> * @param {*} value The value to repeat.
<a name="line1365"></a> * @param {number} n The repeat count.
<a name="line1366"></a> * @return {!Array} An array with the repeated value.
<a name="line1367"></a> */
<a name="line1368"></a>goog.array.repeat = function(value, n) {
<a name="line1369"></a>  var array = [];
<a name="line1370"></a>  for (var i = 0; i &lt; n; i++) {
<a name="line1371"></a>    array[i] = value;
<a name="line1372"></a>  }
<a name="line1373"></a>  return array;
<a name="line1374"></a>};
<a name="line1375"></a>
<a name="line1376"></a>
<a name="line1377"></a>/**
<a name="line1378"></a> * Returns an array consisting of every argument with all arrays
<a name="line1379"></a> * expanded in-place recursively.
<a name="line1380"></a> *
<a name="line1381"></a> * @param {...*} var_args The values to flatten.
<a name="line1382"></a> * @return {!Array} An array containing the flattened values.
<a name="line1383"></a> */
<a name="line1384"></a>goog.array.flatten = function(var_args) {
<a name="line1385"></a>  var result = [];
<a name="line1386"></a>  for (var i = 0; i &lt; arguments.length; i++) {
<a name="line1387"></a>    var element = arguments[i];
<a name="line1388"></a>    if (goog.isArray(element)) {
<a name="line1389"></a>      result.push.apply(result, goog.array.flatten.apply(null, element));
<a name="line1390"></a>    } else {
<a name="line1391"></a>      result.push(element);
<a name="line1392"></a>    }
<a name="line1393"></a>  }
<a name="line1394"></a>  return result;
<a name="line1395"></a>};
<a name="line1396"></a>
<a name="line1397"></a>
<a name="line1398"></a>/**
<a name="line1399"></a> * Rotates an array in-place. After calling this method, the element at
<a name="line1400"></a> * index i will be the element previously at index (i - n) %
<a name="line1401"></a> * array.length, for all values of i between 0 and array.length - 1,
<a name="line1402"></a> * inclusive.
<a name="line1403"></a> *
<a name="line1404"></a> * For example, suppose list comprises [t, a, n, k, s]. After invoking
<a name="line1405"></a> * rotate(array, 1) (or rotate(array, -4)), array will comprise [s, t, a, n, k].
<a name="line1406"></a> *
<a name="line1407"></a> * @param {!Array.&lt;T&gt;} array The array to rotate.
<a name="line1408"></a> * @param {number} n The amount to rotate.
<a name="line1409"></a> * @return {!Array.&lt;T&gt;} The array.
<a name="line1410"></a> * @template T
<a name="line1411"></a> */
<a name="line1412"></a>goog.array.rotate = function(array, n) {
<a name="line1413"></a>  goog.asserts.assert(array.length != null);
<a name="line1414"></a>
<a name="line1415"></a>  if (array.length) {
<a name="line1416"></a>    n %= array.length;
<a name="line1417"></a>    if (n &gt; 0) {
<a name="line1418"></a>      goog.array.ARRAY_PROTOTYPE_.unshift.apply(array, array.splice(-n, n));
<a name="line1419"></a>    } else if (n &lt; 0) {
<a name="line1420"></a>      goog.array.ARRAY_PROTOTYPE_.push.apply(array, array.splice(0, -n));
<a name="line1421"></a>    }
<a name="line1422"></a>  }
<a name="line1423"></a>  return array;
<a name="line1424"></a>};
<a name="line1425"></a>
<a name="line1426"></a>
<a name="line1427"></a>/**
<a name="line1428"></a> * Creates a new array for which the element at position i is an array of the
<a name="line1429"></a> * ith element of the provided arrays.  The returned array will only be as long
<a name="line1430"></a> * as the shortest array provided; additional values are ignored.  For example,
<a name="line1431"></a> * the result of zipping [1, 2] and [3, 4, 5] is [[1,3], [2, 4]].
<a name="line1432"></a> *
<a name="line1433"></a> * This is similar to the zip() function in Python.  See {@link
<a name="line1434"></a> * http://docs.python.org/library/functions.html#zip}
<a name="line1435"></a> *
<a name="line1436"></a> * @param {...!goog.array.ArrayLike} var_args Arrays to be combined.
<a name="line1437"></a> * @return {!Array.&lt;!Array&gt;} A new array of arrays created from provided arrays.
<a name="line1438"></a> */
<a name="line1439"></a>goog.array.zip = function(var_args) {
<a name="line1440"></a>  if (!arguments.length) {
<a name="line1441"></a>    return [];
<a name="line1442"></a>  }
<a name="line1443"></a>  var result = [];
<a name="line1444"></a>  for (var i = 0; true; i++) {
<a name="line1445"></a>    var value = [];
<a name="line1446"></a>    for (var j = 0; j &lt; arguments.length; j++) {
<a name="line1447"></a>      var arr = arguments[j];
<a name="line1448"></a>      // If i is larger than the array length, this is the shortest array.
<a name="line1449"></a>      if (i &gt;= arr.length) {
<a name="line1450"></a>        return result;
<a name="line1451"></a>      }
<a name="line1452"></a>      value.push(arr[i]);
<a name="line1453"></a>    }
<a name="line1454"></a>    result.push(value);
<a name="line1455"></a>  }
<a name="line1456"></a>};
<a name="line1457"></a>
<a name="line1458"></a>
<a name="line1459"></a>/**
<a name="line1460"></a> * Shuffles the values in the specified array using the Fisher-Yates in-place
<a name="line1461"></a> * shuffle (also known as the Knuth Shuffle). By default, calls Math.random()
<a name="line1462"></a> * and so resets the state of that random number generator. Similarly, may reset
<a name="line1463"></a> * the state of the any other specified random number generator.
<a name="line1464"></a> *
<a name="line1465"></a> * Runtime: O(n)
<a name="line1466"></a> *
<a name="line1467"></a> * @param {!Array} arr The array to be shuffled.
<a name="line1468"></a> * @param {function():number=} opt_randFn Optional random function to use for
<a name="line1469"></a> *     shuffling.
<a name="line1470"></a> *     Takes no arguments, and returns a random number on the interval [0, 1).
<a name="line1471"></a> *     Defaults to Math.random() using JavaScript&#39;s built-in Math library.
<a name="line1472"></a> */
<a name="line1473"></a>goog.array.shuffle = function(arr, opt_randFn) {
<a name="line1474"></a>  var randFn = opt_randFn || Math.random;
<a name="line1475"></a>
<a name="line1476"></a>  for (var i = arr.length - 1; i &gt; 0; i--) {
<a name="line1477"></a>    // Choose a random array index in [0, i] (inclusive with i).
<a name="line1478"></a>    var j = Math.floor(randFn() * (i + 1));
<a name="line1479"></a>
<a name="line1480"></a>    var tmp = arr[i];
<a name="line1481"></a>    arr[i] = arr[j];
<a name="line1482"></a>    arr[j] = tmp;
<a name="line1483"></a>  }
<a name="line1484"></a>};
</pre>


</body>
</html>
